# !/usr/bin/env python
# -*- coding: utf-8 -*-


def fibonacci_search(num_arr, num):
    length = len(num_arr)

    # 构建费波拉契数列
    f_size = 100
    f_arr = [_ for _ in range(f_size)]
    f_arr[0] = 0
    f_arr[1] = 1
    for i in range(2, f_size):
        f_arr[i] = f_arr[i - 1] + f_arr[i - 2]
    start = 0
    end = length - 1
    index = 0
    while f_arr[index] < length:
        index += 1
    tmp_arr = num_arr[0:length]
    tmp_index = length
    while tmp_index < f_arr[index]:
        tmp_arr.append(num_arr[end])
        tmp_index += 1

    while start <= end and index >= 0:
        mid = start + f_arr[index - 1] - 1
        if tmp_arr[mid] == num:
            return min(mid, end)
        elif tmp_arr[mid] > num:
            end = mid - 1
            index -= 1
        else:
            start = mid + 1
            index -= 2
    return None


if __name__ == '__main__':
    arr = [1, 3, 5, 7, 10, 15, 20, 100, 120]
    res = fibonacci_search(arr, 120)
    print(res)
